class Solution {
public:
    vector<int> inventoryManagement(vector<int>& stock, int cnt) {
        srand(time(NULL));
        QuickSort(stock, 0, stock.size() - 1, cnt);
        return { stock.begin(), stock.begin() + cnt };
    }

    void QuickSort(vector<int>& nums, int begin, int end, int k)
    {
        if (begin >= end)
            return;
        int key = nums[rand() % (end - begin + 1) + begin];
        int left = begin - 1, right = end + 1, i = begin;
        while (i < right)
        {
            if (key > nums[i])
                swap(nums[++left], nums[i++]);
            else if (key == nums[i])
                i++;
            else
                swap(nums[--right], nums[i]);
        }
        int a = left - begin + 1, b = right - left - 1;
        if (k < a)
            QuickSort(nums, begin, left, k);
        else if (k <= a + b)
            return;
        else
            return QuickSort(nums, right, end, k - a - b);
    }
};